// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/cert/ct_log_verifier.h"

#include <stdint.h>

#include <memory>
#include <string>

#include "base/strings/string_number_conversions.h"
#include "base/time/time.h"
#include "crypto/secure_hash.h"
#include "net/base/hash_value.h"
#include "net/cert/ct_log_verifier_util.h"
#include "net/cert/merkle_consistency_proof.h"
#include "net/cert/signed_certificate_timestamp.h"
#include "net/cert/signed_tree_head.h"
#include "net/test/ct_test_util.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace net {

namespace {

    // Calculate the power of two nearest to, but less than, |n|.
    // |n| must be at least 2.
    uint64_t CalculateNearestPowerOfTwo(uint64_t n)
    {
        DCHECK_GT(n, 1u);

        uint64_t ret = UINT64_C(1) << 63;
        while (ret >= n)
            ret >>= 1;

        return ret;
    }

    // The following structures, TestVector and ProofTestVector are used for
    // definining test proofs later on.

    // A single hash node.
    struct TestVector {
        const char* const str;
        size_t length_bytes;
    };

    // A single consistency proof. Contains the old and new tree sizes
    // (snapshot1 and snapshot2), the length of the proof (proof_length) and
    // at most 3 proof nodes (all test proofs will be for a tree of size 8).
    struct ProofTestVector {
        uint64_t snapshot1;
        uint64_t snapshot2;
        size_t proof_length;
        TestVector proof[3];
    };

    // All test data replicated from
    // https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc
    // A hash of the empty string.
    const TestVector kSHA256EmptyTreeHash = {
        "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32
    };

    // Node hashes for a sample tree of size 8 (each element in this array is
    // a node hash, not leaf data; order represents order of the nodes in the tree).
    const TestVector kSHA256Roots[8] = {
        { "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32 },
        { "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32 },
        { "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 32 },
        { "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32 },
        { "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 32 },
        { "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 32 },
        { "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32 },
        { "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32 }
    };

    // A collection of consistency proofs between various sub-trees of the tree
    // defined by |kSHA256Roots|.
    const ProofTestVector kSHA256Proofs[4] = {
        // Empty consistency proof between trees of the same size (1).
        { 1, 1, 0, { { "", 0 }, { "", 0 }, { "", 0 } } },
        // Consistency proof between tree of size 1 and tree of size 8, with 3
        // nodes in the proof.
        { 1,
            8,
            3,
            { { "96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32 },
                { "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32 },
                { "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4",
                    32 } } },
        // Consistency proof between tree of size 6 and tree of size 8, with 3
        // nodes in the proof.
        { 6,
            8,
            3,
            { { "0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", 32 },
                { "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32 },
                { "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
                    32 } } },
        // Consistency proof between tree of size 2 and tree of size 5, with 2
        // nodes in the proof.
        { 2,
            5,
            2,
            { { "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32 },
                { "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32 },
                { "", 0 } } }
    };

    // Decodes a hexadecimal string into the binary data it represents.
    std::string HexToBytes(const char* hex_data, size_t hex_data_length)
    {
        std::vector<uint8_t> output;
        std::string result;
        std::string hex_data_input(hex_data, hex_data_length);
        if (base::HexStringToBytes(hex_data, &output))
            result.assign(reinterpret_cast<const char*>(&output[0]), output.size());
        return result;
    }

    std::string GetEmptyTreeHash()
    {
        return HexToBytes(kSHA256EmptyTreeHash.str,
            kSHA256EmptyTreeHash.length_bytes);
    }

    // Creates a ct::MerkleConsistencyProof and returns the result of
    // calling log->VerifyConsistencyProof with that proof and snapshots.
    bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log,
        uint64_t old_tree_size,
        const std::string& old_tree_root,
        uint64_t new_tree_size,
        const std::string& new_tree_root,
        const std::vector<std::string>& proof)
    {
        return log->VerifyConsistencyProof(
            ct::MerkleConsistencyProof(log->key_id(), proof, old_tree_size,
                new_tree_size),
            old_tree_root, new_tree_root);
    }

    class CTLogVerifierTest : public ::testing::Test {
    public:
        CTLogVerifierTest() { }

        void SetUp() override
        {
            log_ = CTLogVerifier::Create(ct::GetTestPublicKey(), "testlog",
                "https://ct.example.com");

            ASSERT_TRUE(log_);
            ASSERT_EQ(log_->key_id(), ct::GetTestPublicKeyId());
        }

        // Given a consistency proof between two snapshots of the tree, asserts that
        // it verifies and no other combination of snapshots and proof nodes verifies.
        void VerifierConsistencyCheck(int snapshot1,
            int snapshot2,
            const std::string& root1,
            const std::string& root2,
            const std::vector<std::string>& proof)
        {
            // Verify the original consistency proof.
            EXPECT_TRUE(
                VerifyConsistencyProof(log_, snapshot1, root1, snapshot2, root2, proof))
                << " " << snapshot1 << " " << snapshot2;

            if (proof.empty()) {
                // For simplicity test only non-trivial proofs that have root1 != root2
                // snapshot1 != 0 and snapshot1 != snapshot2.
                return;
            }

            // Wrong snapshot index: The proof checking code should not accept
            // as a valid proof a proof for a tree size different than the original
            // size it was produced for.
            // Test that this is not the case for off-by-one changes.
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 - 1, root1, snapshot2,
                root2, proof));
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 + 1, root1, snapshot2,
                root2, proof));
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 ^ 2, root1, snapshot2,
                root2, proof));

            // Test that the proof is not accepted for trees with wrong tree height.
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2 * 2,
                root2, proof));
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2 / 2,
                root2, proof));

            // Test that providing the wrong input root fails checking an
            // otherwise-valid proof.
            const std::string wrong_root("WrongRoot");
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                wrong_root, proof));
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, wrong_root, snapshot2,
                root2, proof));
            // Test that swapping roots fails checking an otherwise-valid proof (that
            // the right root is used for each calculation).
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root2, snapshot2,
                root1, proof));

            // Variations of wrong proofs, all of which should be rejected.
            std::vector<std::string> wrong_proof;
            // Empty proof.
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                root2, wrong_proof));

            // Modify a single element in the proof.
            for (size_t j = 0; j < proof.size(); ++j) {
                wrong_proof = proof;
                wrong_proof[j] = GetEmptyTreeHash();
                EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                    root2, wrong_proof));
            }

            // Add garbage at the end of the proof.
            wrong_proof = proof;
            wrong_proof.push_back(std::string());
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                root2, wrong_proof));
            wrong_proof.pop_back();

            wrong_proof.push_back(proof.back());
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                root2, wrong_proof));
            wrong_proof.pop_back();

            // Remove a node from the end.
            wrong_proof.pop_back();
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                root2, wrong_proof));

            // Add garbage in the beginning of the proof.
            wrong_proof.clear();
            wrong_proof.push_back(std::string());
            wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                root2, wrong_proof));

            wrong_proof[0] = proof[0];
            EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                root2, wrong_proof));
        }

    protected:
        scoped_refptr<const CTLogVerifier> log_;
    };

    TEST_F(CTLogVerifierTest, VerifiesCertSCT)
    {
        ct::LogEntry cert_entry;
        ct::GetX509CertLogEntry(&cert_entry);

        scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
        ct::GetX509CertSCT(&cert_sct);

        EXPECT_TRUE(log_->Verify(cert_entry, *cert_sct.get()));
    }

    TEST_F(CTLogVerifierTest, VerifiesPrecertSCT)
    {
        ct::LogEntry precert_entry;
        ct::GetPrecertLogEntry(&precert_entry);

        scoped_refptr<ct::SignedCertificateTimestamp> precert_sct;
        ct::GetPrecertSCT(&precert_sct);

        EXPECT_TRUE(log_->Verify(precert_entry, *precert_sct.get()));
    }

    TEST_F(CTLogVerifierTest, FailsInvalidTimestamp)
    {
        ct::LogEntry cert_entry;
        ct::GetX509CertLogEntry(&cert_entry);

        scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
        ct::GetX509CertSCT(&cert_sct);

        // Mangle the timestamp, so that it should fail signature validation.
        cert_sct->timestamp = base::Time::Now();

        EXPECT_FALSE(log_->Verify(cert_entry, *cert_sct.get()));
    }

    TEST_F(CTLogVerifierTest, FailsInvalidLogID)
    {
        ct::LogEntry cert_entry;
        ct::GetX509CertLogEntry(&cert_entry);

        scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
        ct::GetX509CertSCT(&cert_sct);

        // Mangle the log ID, which should cause it to match a different log before
        // attempting signature validation.
        cert_sct->log_id.assign(cert_sct->log_id.size(), '\0');

        EXPECT_FALSE(log_->Verify(cert_entry, *cert_sct.get()));
    }

    TEST_F(CTLogVerifierTest, VerifiesValidSTH)
    {
        ct::SignedTreeHead sth;
        ASSERT_TRUE(ct::GetSampleSignedTreeHead(&sth));
        EXPECT_TRUE(log_->VerifySignedTreeHead(sth));
    }

    TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidSTH)
    {
        ct::SignedTreeHead sth;
        ASSERT_TRUE(ct::GetSampleSignedTreeHead(&sth));
        sth.sha256_root_hash[0] = '\x0';
        EXPECT_FALSE(log_->VerifySignedTreeHead(sth));
    }

    TEST_F(CTLogVerifierTest, VerifiesValidEmptySTH)
    {
        ct::SignedTreeHead sth;
        ASSERT_TRUE(ct::GetSampleEmptySignedTreeHead(&sth));
        EXPECT_TRUE(log_->VerifySignedTreeHead(sth));
    }

    TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidEmptySTH)
    {
        ct::SignedTreeHead sth;
        ASSERT_TRUE(ct::GetBadEmptySignedTreeHead(&sth));
        EXPECT_FALSE(log_->VerifySignedTreeHead(sth));
    }

    // Test that excess data after the public key is rejected.
    TEST_F(CTLogVerifierTest, ExcessDataInPublicKey)
    {
        std::string key = ct::GetTestPublicKey();
        key += "extra";

        scoped_refptr<const CTLogVerifier> log = CTLogVerifier::Create(key, "testlog", "https://ct.example.com");
        EXPECT_FALSE(log);
    }

    TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_EmptyProof)
    {
        std::vector<std::string> empty_proof;
        std::string root1(GetEmptyTreeHash()), root2(GetEmptyTreeHash());

        // Snapshots that are always consistent, because they are either
        // from an empty tree to a non-empty one or for trees of the same
        // size.
        EXPECT_TRUE(VerifyConsistencyProof(log_, 0, root1, 0, root2, empty_proof));
        EXPECT_TRUE(VerifyConsistencyProof(log_, 0, root1, 1, root2, empty_proof));
        EXPECT_TRUE(VerifyConsistencyProof(log_, 1, root1, 1, root2, empty_proof));

        // Invalid consistency proofs.
        // Time travel to the past.
        EXPECT_FALSE(VerifyConsistencyProof(log_, 1, root1, 0, root2, empty_proof));
        EXPECT_FALSE(VerifyConsistencyProof(log_, 2, root1, 1, root2, empty_proof));
        // Proof between two trees of different size can never be empty.
        EXPECT_FALSE(VerifyConsistencyProof(log_, 1, root1, 2, root2, empty_proof));
    }

    TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_MismatchingRoots)
    {
        std::vector<std::string> empty_proof;
        std::string root2;
        const std::string empty_tree_hash(GetEmptyTreeHash());

        // Roots don't match.
        EXPECT_FALSE(
            VerifyConsistencyProof(log_, 0, empty_tree_hash, 0, root2, empty_proof));
        EXPECT_FALSE(
            VerifyConsistencyProof(log_, 1, empty_tree_hash, 1, root2, empty_proof));
    }

    TEST_F(CTLogVerifierTest,
        VerifiesConsistencyProofEdgeCases_MatchingRootsNonEmptyProof)
    {
        const std::string empty_tree_hash(GetEmptyTreeHash());

        std::vector<std::string> proof;
        proof.push_back(empty_tree_hash);

        // Roots match and the tree size is either the same or the old tree size is 0,
        // but the proof is not empty (the verification code should not accept
        // proofs with redundant nodes in this case).
        proof.push_back(empty_tree_hash);
        EXPECT_FALSE(VerifyConsistencyProof(log_, 0, empty_tree_hash, 0,
            empty_tree_hash, proof));
        EXPECT_FALSE(VerifyConsistencyProof(log_, 0, empty_tree_hash, 1,
            empty_tree_hash, proof));
        EXPECT_FALSE(VerifyConsistencyProof(log_, 1, empty_tree_hash, 1,
            empty_tree_hash, proof));
    }

    TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs)
    {
        std::vector<std::string> proof;
        std::string root1, root2;

        // Known good proofs.
        for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) {
            proof.clear();
            for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) {
                const TestVector& v = kSHA256Proofs[i].proof[j];
                proof.push_back(HexToBytes(v.str, v.length_bytes));
            }
            const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
            const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
            const TestVector& old_root = kSHA256Roots[snapshot1 - 1];
            const TestVector& new_root = kSHA256Roots[snapshot2 - 1];
            VerifierConsistencyCheck(
                snapshot1, snapshot2, HexToBytes(old_root.str, old_root.length_bytes),
                HexToBytes(new_root.str, new_root.length_bytes), proof);
        }
    }

    const char kLeafPrefix[] = { '\x00' };

    // Reference implementation of RFC6962.
    // This allows generation of arbitrary-sized Merkle trees and consistency
    // proofs between them for testing the consistency proof validation
    // code.
    class TreeHasher {
    public:
        static std::string HashEmpty()
        {
            return HexToBytes(kSHA256EmptyTreeHash.str,
                kSHA256EmptyTreeHash.length_bytes);
        }

        static std::string HashLeaf(const std::string& leaf)
        {
            SHA256HashValue sha256;
            memset(sha256.data, 0, sizeof(sha256.data));

            std::unique_ptr<crypto::SecureHash> hash(
                crypto::SecureHash::Create(crypto::SecureHash::SHA256));
            hash->Update(kLeafPrefix, 1);
            hash->Update(leaf.data(), leaf.size());
            hash->Finish(sha256.data, sizeof(sha256.data));

            return std::string(reinterpret_cast<const char*>(sha256.data),
                sizeof(sha256.data));
        }
    };

    // Reference implementation of Merkle hash, for cross-checking.
    // Recursively calculates the hash of the root given the leaf data
    // specified in |inputs|.
    std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size)
    {
        if (!input_size)
            return TreeHasher::HashEmpty();
        if (input_size == 1)
            return TreeHasher::HashLeaf(inputs[0]);

        const uint64_t split = CalculateNearestPowerOfTwo(input_size);

        return ct::internal::HashNodes(
            ReferenceMerkleTreeHash(&inputs[0], split),
            ReferenceMerkleTreeHash(&inputs[split], input_size - split));
    }

    // Reference implementation of snapshot consistency. Returns a
    // consistency proof between two snapshots of the tree designated
    // by |inputs|.
    // Call with have_root1 = true.
    std::vector<std::string> ReferenceSnapshotConsistency(std::string* inputs,
        uint64_t snapshot2,
        uint64_t snapshot1,
        bool have_root1)
    {
        std::vector<std::string> proof;
        if (snapshot1 == 0 || snapshot1 > snapshot2)
            return proof;
        if (snapshot1 == snapshot2) {
            // Consistency proof for two equal subtrees is empty.
            if (!have_root1) {
                // Record the hash of this subtree unless it's the root for which
                // the proof was originally requested. (This happens when the snapshot1
                // tree is balanced.)
                proof.push_back(ReferenceMerkleTreeHash(inputs, snapshot1));
            }
            return proof;
        }

        // 0 < snapshot1 < snapshot2
        const uint64_t split = CalculateNearestPowerOfTwo(snapshot2);

        std::vector<std::string> subproof;
        if (snapshot1 <= split) {
            // Root of snapshot1 is in the left subtree of snapshot2.
            // Prove that the left subtrees are consistent.
            subproof = ReferenceSnapshotConsistency(inputs, split, snapshot1, have_root1);
            proof.insert(proof.end(), subproof.begin(), subproof.end());
            // Record the hash of the right subtree (only present in snapshot2).
            proof.push_back(ReferenceMerkleTreeHash(&inputs[split], snapshot2 - split));
        } else {
            // Snapshot1 root is at the same level as snapshot2 root.
            // Prove that the right subtrees are consistent. The right subtree
            // doesn't contain the root of snapshot1, so set have_root1 = false.
            subproof = ReferenceSnapshotConsistency(&inputs[split], snapshot2 - split,
                snapshot1 - split, false);
            proof.insert(proof.end(), subproof.begin(), subproof.end());
            // Record the hash of the left subtree (equal in both trees).
            proof.push_back(ReferenceMerkleTreeHash(&inputs[0], split));
        }
        return proof;
    }

// Times out on Win7 test bot.  http://crbug.com/598406
#if defined(OS_WIN)
#define MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator \
    DISABLED_VerifiesValidConsistencyProofsFromReferenceGenerator
#else
#define MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator \
    VerifiesValidConsistencyProofsFromReferenceGenerator
#endif
    TEST_F(CTLogVerifierTest,
        MAYBE_VerifiesValidConsistencyProofsFromReferenceGenerator)
    {
        std::vector<std::string> data;
        for (int i = 0; i < 256; ++i)
            data.push_back(std::string(1, i));

        std::vector<std::string> proof;
        std::string root1, root2;
        // More tests with reference proof generator.
        for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
            root2 = ReferenceMerkleTreeHash(data.data(), tree_size);
            // Repeat for each snapshot in range.
            for (size_t snapshot = 1; snapshot <= tree_size; ++snapshot) {
                proof = ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
                root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
                VerifierConsistencyCheck(snapshot, tree_size, root1, root2, proof);
            }
        }
    }

} // namespace

} // namespace net
